package com.gitee.jsbd.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序 原地排序 稳定  （最好：O(n)   最坏：O(n^2) 平均：O(n^2)）
 * <p>
 * 插入排序方法分直接插入排序和折半插入排序两种，这里是直接插入排序算法的实现
 * 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
 * </p>
 */
public class InsertSort {
    
    public static void insertSort(int[] data) {

        for (int i = 1; i < data.length; i++) {

            int value = data[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (data[j] > value) {
                    data[j + 1] = data[j];
                } else {
                    break;
                }
            }
            data[j + 1] = value;

            System.out.print("第" + i + "次排序后：");
            System.out.println(Arrays.toString(data));
        }

    }


    public static void main(String[] args) {
        int[] data = new int[]{5, 8, 7, 9, 1, 2};
        System.out.print("==初始化==：");
        System.out.println(Arrays.toString(data));

        insertSort(data);

        System.out.println(Arrays.toString(data));
    }

}
